package gold.digger;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC120 {


    public int minimumTotal(List<List<Integer>> triangle) {
        if (null == triangle || triangle.size() <= 0) {
            return 0;
        }

        int size = triangle.size();
        int[][] dp = new int[2][size];
        Arrays.fill(dp[0], triangle.get(0).get(0));
        Arrays.fill(dp[1], triangle.get(0).get(0));

        int curIndicator = 0, lastIndicator = 1, minPathSum = Integer.MAX_VALUE;
        // loops size - 1 times to update dp array
        for (int i = 1; i < size; i++) {
            curIndicator = i % 2;
            lastIndicator = (i - 1) % 2;
            for (int j = 0; j <= i; j++) {
                if (j == 0) {
                    dp[curIndicator][j] = triangle.get(i).get(j) + dp[lastIndicator][j];
                } else if (j == i) {
                    dp[curIndicator][j] = triangle.get(i).get(j) + dp[lastIndicator][j - 1];
                } else {
                    dp[curIndicator][j] = triangle.get(i).get(j) + Math.min(dp[lastIndicator][j - 1], dp[lastIndicator][j]);
                }
            }
        }

        for (int i = 0; i < size; i++) {
            minPathSum = Math.min(minPathSum, dp[curIndicator][i]);
        }

        return minPathSum;
    }

    public static void main(String[] args) {
        LC120 an = new LC120();
        List<List<Integer>> triangle = new ArrayList<>();

        /**
         * [
         [2],
         [3,4],
         [6,5,7],
         [4,1,8,3]
         ]
         */

        triangle.add(Arrays.asList(2));
        triangle.add(Arrays.asList(3, 4));
        triangle.add(Arrays.asList(6, 5, 7));
        triangle.add(Arrays.asList(4, 1, 8, 3));

        System.out.println(an.minimumTotal(triangle));
    }
}
